package com.fr.lintcode;

import org.junit.Test;

public class Q440 {

	/**
	 * @param A: an integer array
	 * @param V: an integer array
	 * @param m: An integer
	 * @return: an array
	 */
	public int backPackIII(int[] A, int[] V, int m) {
		// write your code here

		// write your code here
		if (A == null) {
			return 0;
		}
		int dp[] = new int[m + 1];
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j < A.length; j++) {
				if (A[j] <= i) {
					dp[i] = Math.max(dp[i], dp[i - A[j]] + V[j]);
				}
			}
		}
		return dp[m];

	}

	@Test
	public void testA() {
		int[] A = { 2, 3, 5, 7 };
		int[] V = { 1, 5, 2, 4 };
		int m = 10;
		int rs = backPackIII(A, V, m);
		System.out.println(rs);
	}

}
